package net.tp.struct.bst;

import net.tp.struct.tree.TreePrinter;
import net.tp.struct.tree.AbstractBinNode;
import static net.tp.util.Utils.*;

import java.util.*;
import static java.util.Arrays.*;

/**
 *
 * <p>Treap.</p>
 *
 * <p>Treap is a competitive data structure to red black tree in terms of speed with simpler implementation.</p>
 *
 * @author Trung Phan
 *
 */
public class Treap<E> {

    private final Comparator<? super E> comparator;

    private TreapNode<E> root;

    private Random random = new Random();

    public Treap() {
        this(naturalComparator());
    }

    public Treap(Comparator<? super E> comparator) {
        this.comparator = comparator;
    }

    public boolean empty() {
        return root ==  null;
    }

    public int size() {
        return root == null ? 0 : root.size;
    }

    public void add(E element) {
        if (root == null) {
            root = new TreapNode<>(element, random.nextDouble());
        }
        else {
            TreapNode<E> n = find(element);
            int cmp = comparator.compare(element, n.element);
            if (cmp != 0) {
                TreapNode<E> newNode = new TreapNode<>(element, random.nextDouble());
                if (cmp < 0) n.bindLeft(newNode);
                else n.bindRight(newNode);

                for (TreapNode<E> i = n; i != null; i.size++, i = i.parent);

                newNode.siftUp();
                if (newNode.parent == null) root = newNode;
            }
        }
    }

    public boolean contains(E element) {
        TreapNode<E> n = find(element);
        return n != null && comparator.compare(element, n.element) == 0;
    }

    public boolean remove(E element) {

        TreapNode<E> n = find(element);
        if (n == null || comparator.compare(element, n.element) != 0) return false;

        n.siftDownToLeaf();
        root = n.getRoot(); // the n might be the root, the sift down will change the root

        for (TreapNode<E> i = n.parent; i != null; i.size--, i = i.parent);

        if (n.parent == null) {
            root = null;
        }
        else if (n.parent.left == n) {
            n.parent.bindLeft(null);
        }
        else {
            n.parent.bindRight(null);
        }
        n.parent = null; n.element = null;

        return false; 
    }

    /**
     * If root != null, return the last non-null node in the searching path for key.
     * @param key
     * @return
     */
    private TreapNode<E> find(E element) {
        if (root == null) return null;

        TreapNode<E> n = root;
        while (true) {
            int c = comparator.compare(element, n.element);
            if (c == 0) {
                return n;
            }
            TreapNode<E> next = c < 0 ? n.left : n.right;
            if (next == null) return n;
            n = next;
        }
    }

    public boolean isValid() {

        return root == null || isValid(root);
    }

    private boolean isValid(TreapNode<E> node) {
        if (node.left != null) {
            if (comparator.compare(node.element, node.left.element) <= 0 || node.priority < node.left.priority) {
                return false;
            }
        }
        else if (node.right != null) {
            if (comparator.compare(node.element, node.right.element) >= 0 || node.priority < node.right.priority) {
                return false;
            }
        }
        return node.size == 1 + (node.left != null ? node.left.size : 0) + (node.right != null ? node.right.size : 0);
    }

    @Override
    public String toString() {
        return TreePrinter.toString(root, TreapNode::getChildren);

    }

    public static class TreapNode<E> extends AbstractBinNode<TreapNode<E>> {

        private E element;

        private double priority;

        public TreapNode(E element, double priority) {
            if (priority < 0.0 || priority > 1.0) throw new IllegalArgumentException();

            this.element = element;
            this.priority = priority;
        }

        public void siftUp() {
            while (parent != null && priority > parent.priority) {
                if (parent.left == this) {
                    parent.rotateRight();
                }
                else {
                    parent.rotateLeft();
                }
            }
        }

        /**
         * sift the node to the leaf. Assume that this node has the lowest priority.
         */
        public void siftDownToLeaf() {
            while (left != null || right != null) {
                if (right == null || (left != null && left.priority >= right.priority)) {
                    rotateRight();
                }
                else {
                    rotateLeft();
                }
            }
        }


        @Override
        public String toString() {
            return element + ":" + priority;
        }
    }

}
